<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Honeycomb Chess Board</title>
    <style>
        .line {
            display: flex;
            align-items: center;
            justify-content: center;
            position: relative;
            margin-bottom: -1.2vw;
            &:nth-child(odd) {
                transform: translateX(-2.5vw);
            }
        }

        .item {
            width: 5vw;
            height: 5vw;
            background: #B5B5B5;
            outline: 1px solid #FF754F;
            clip-path: polygon(50% 1%, 99% 25%, 99% 75%, 50% 99%, 1% 75%, 1% 25%);
            position: relative;
			display: flex;
			align-items: center;
			justify-content: center;
			color: #FFFFFF
        }
		
		.item img {
            width: 80%;
            height: 80%;
            object-fit: cover;
        }
    </style>
</head>
<body>
    <div id="container">
    </div>

    <script>
		class GameBoard {
			constructor(rows = 11, cols = 11) {
				this.rows = rows;
				this.cols = cols;
				this.beginRows = Math.floor(rows / 2);
				this.beginCols = Math.floor(cols / 2);
				this.currentRow = this.beginRows;
				this.currentCol = this.beginCols;
				this.moveLock = 0;
				this.map = this.createMap();
				this.cost = this.createCostMap();
				this.distances = this.createDistanceMap();
				//this.initializeBoard();
				this.calCost();
			}

			createMap() {
				const map = new Array(this.rows);
				for (let i = 0; i < this.rows; i++) {
					map[i] = new Array(this.cols).fill(0);
				}
				this.setObstaclesAndCat(map);
				return map;
			}

			createCostMap() {
				const cost = new Array(this.rows);
				for (let i = 0; i < this.rows; i++) {
					cost[i] = new Array(this.cols).fill(10);
				}
				this.setObstacleCosts(cost);
				return cost;
			}

			createDistanceMap() {
				const distances = new Array(this.rows);
				for (let i = 0; i < this.rows; i++) {
					distances[i] = new Array(this.cols).fill(99999);
				}
				distances[this.currentRow][this.currentCol] = 0;
				return distances;
			}

			setObstaclesAndCat(map) {
				map[this.beginRows][this.beginCols] = 1;
				map[0][4] = 2;
				map[0][10] = 2;
				map[1][3] = 2;
				map[2][4] = 2;
				map[3][2] = 2;
				map[4][7] = 2;
				map[4][10] = 2;
				map[6][6] = 2;
				map[6][9] = 2;
				map[7][4] = 2;
				map[7][7] = 2;
				map[9][1] = 2;
				map[9][7] = 2;
				map[10][1] = 2;
			}

			setObstacleCosts(cost) {
				for (let i = 0; i < this.rows; i++) {
					for (let j = 0; j < this.rows; j++) {
						if (this.map[i][j] == 1) {
							cost[i][j] = 0;
						} else if (this.map[i][j] == 2) {
							cost[i][j] = 99999;
						} else {
							cost[i][j] = 10;
						}
					}
				}
			}

			getBackgroundColor(row, col) {
				if (this.map[row][col] == 1) {
					return '#000';
				} else if (this.map[row][col] == 2) {
					return '#FF754F';
				} else {
					return '#B5B5B5';
				}
			}

			updateCell(row, col) {
				this.map[row][col] = 2;
				this.cost[row][col] = 99999;
				let cell = document.querySelector(`.item[data-row="${row}"][data-col="${col}"]`);
				cell.style.backgroundColor = '#FF754F';
			}

			calCost() {
				this.setObstacleCosts(this.cost);
				
				for (let i = 0; i < this.rows; i++) {
					for (let j = 0; j < this.cols; j++) {
						let tmp = this.getNeighborsType(i, j);
						for (let k = 0; k < tmp.length; k++) {
							if(tmp[k] == 2) {
								this.cost[i][j] ++;
							}
						}
					}
				}
			}

			displayText(arr) {
				for (let i = 0; i < arr.length; i++) {
					for (let j = 0; j < arr[i].length; j++) {
						let cell = document.querySelector(`.item[data-row="${i}"][data-col="${j}"]`);
						if (cell) {
							if (this.map[i][j] == 0) {
								cell.textContent = arr[i][j];
							} else if (this.map[i][j] != 1) {
								cell.textContent = '';
							}
						}
					}
				}
			}

			calPath(row, col) {
				console.info('开始计算路径');
				let queue = [];
				queue.push([row, col]);
				let visited = new Array(this.rows);
				let distances = new Array(this.rows);
				let paths = new Array(this.rows);
				for (let i = 0; i < this.rows; i++) {
					visited[i] = new Array(this.cols);
					distances[i] = new Array(this.cols);
					paths[i] = new Array(this.cols);
					for (let j = 0; j < this.cols; j++) {
						visited[i][j] = 0;
						distances[i][j] = 99999;
						paths[i][j] = null;
					}
				}
				visited[row][col] = 1;
				distances[row][col] = 0;

				while(queue.length > 0) {
					let s = queue.shift();
					
					let neighbors = this.getNeighbors(s[0], s[1]);
					
					for (let i = 0; i < neighbors.length; i++) {
						let t = neighbors[i];
						if (t == null) {
							console.info('找到出口(' + s[0] + '，' + s[1] + ')，距离是：' + distances[s[0]][s[1]]);
							
							this.displayText(distances);

							let next = [s[0], s[1]];
							let p = paths[s[0]][s[1]];
							while (p != null) {
								if(p[0] == row && p[1] == col) {
									break;
								}
								next = p;
								p = paths[p[0]][p[1]];
							}

							//let scell = document.querySelector(`.item[data-row="${row}"][data-col="${col}"]`);
							//let tcell = document.querySelector(`.item[data-row="${next[0]}"][data-col="${next[1]}"]`);
							//scell.style.backgroundColor = '#B5B5B5';
							//tcell.style.backgroundColor = '#000';
							//this.currentRow = next[0];
							//this.currentCol = next[1];
							
							//this.map[row][col] = 0;
							//this.cost[row][col] = 10;
							//this.map[next[0]][next[1]] = 1;
							//this.cost[next[0]][next[1]] = 99999;
							//this.calCost();
							this.moveCat(row, col, next[0], next[1]);
							this.calCost();
							return 1;
						} else if (this.map[t[0]][t[1]] == 0) {
							if(distances[t[0]][t[1]] > distances[s[0]][s[1]] + this.cost[t[0]][t[1]]) {
								distances[t[0]][t[1]] = distances[s[0]][s[1]] + this.cost[t[0]][t[1]];
								if (visited[t[0]][t[1]] == 0) {
									queue.push([t[0], t[1]]);
									visited[t[0]][t[1]] = 1;
									paths[t[0]][t[1]] = [s[0], s[1]];
								}
							}
						}
					}
				}
							
				this.displayText(distances);
				console.info('没找到出口');
				return -1;
			}

			calPathAsync(row, col) {
				return new Promise((resolve) => {
					console.info('开始计算路径');
					let queue = [];
					queue.push([row, col]);
					let visited = new Array(this.rows);
					let distances = new Array(this.rows);
					let paths = new Array(this.rows);
					for (let i = 0; i < this.rows; i++) {
						visited[i] = new Array(this.cols);
						distances[i] = new Array(this.cols);
						paths[i] = new Array(this.cols);
						for (let j = 0; j < this.cols; j++) {
							visited[i][j] = 0;
							distances[i][j] = 99999;
							paths[i][j] = null;
						}
					}
					visited[row][col] = 1;
					distances[row][col] = 0;

					while(queue.length > 0) {
						let s = queue.shift();
						
						let neighbors = this.getNeighbors(s[0], s[1]);
						
						for (let i = 0; i < neighbors.length; i++) {
							let t = neighbors[i];
							if (t == null) {
								console.info('找到出口(' + s[0] + '，' + s[1] + ')，距离是：' + distances[s[0]][s[1]]);
								
								this.displayText(distances);

								let next = [s[0], s[1]];
								let p = paths[s[0]][s[1]];
								while (p != null) {
									if(p[0] == row && p[1] == col) {
										break;
									}
									next = p;
									p = paths[p[0]][p[1]];
								}
								let scell = document.querySelector(`.item[data-row="${row}"][data-col="${col}"]`);
								let tcell = document.querySelector(`.item[data-row="${next[0]}"][data-col="${next[1]}"]`);
								scell.style.backgroundColor = '#B5B5B5';
								tcell.style.backgroundColor = '#000';
								this.currentRow = next[0];
								this.currentCol = next[1];
								
								this.map[row][col] = 0;
								this.cost[row][col] = 10;
								this.map[next[0]][next[1]] = 1;
								this.cost[next[0]][next[1]] = 99999;
								this.calCost();
								this.moveLock = 0;
								resolve(1);
								return;
							} else if (this.map[t[0]][t[1]] == 0) {
								if(distances[t[0]][t[1]] > distances[s[0]][s[1]] + this.cost[t[0]][t[1]]) {
									distances[t[0]][t[1]] = distances[s[0]][s[1]] + this.cost[t[0]][t[1]];
									if (visited[t[0]][t[1]] == 0) {
										queue.push([t[0], t[1]]);
										visited[t[0]][t[1]] = 1;
										paths[t[0]][t[1]] = [s[0], s[1]];
									}
								}
							}
						}
					}
								
					this.displayText(distances);
					console.info('没找到出口');
					resolve(-1);
				});
			}

			moveCat(from_row, from_col, to_row, to_col) {
				if(from_row == to_row && from_col == to_col) return;
				if(this.map[to_row][to_col] != 0) return;

				let from_cell = document.querySelector(`.item[data-row="${from_row}"][data-col="${from_col}"]`);
				let to_cell = document.querySelector(`.item[data-row="${to_row}"][data-col="${to_col}"]`);
				
				let img = from_cell.querySelector('img');
				if (img) {
					from_cell.removeChild(img);
				}

				img = document.createElement('img');
				img.src = 'cat.png';
				img.alt = 'A cute cat';
				to_cell.appendChild(img);

				this.map[from_row][from_col] = 0;
				this.map[to_row][to_col] = 1;

				this.currentRow = to_row;
				this.currentCol = to_col;
			}

			getLeft(row, col) {
				if(col - 1 >= 0) {
					//console.info(row + '，' + col + ' 的左边是：' + (row) + '，' + (col - 1));
					//return map[row][col - 1];
					return new Array(row, col - 1);
				}
				return null;
			}

			getTopLeft(row, col) {
				if(row % 2 == 0) {
					if(row - 1 >= 0 && col - 1 >= 0) {
						//console.info(row + '，' + col + ' 的左上是：' + (row - 1) + '，' + (col - 1));
						//return map[row - 1][col - 1];
						return new Array(row - 1, col - 1);
					}
				} else {
					if(row - 1 >= 0) {
						//console.info(row + '，' + col + ' 的左上是：' + (row - 1) + '，' + (col));
						//return map[row - 1][col];
						return new Array(row - 1, col);
					}
				}
				return null;
			}

			getTopRight(row, col) {
				if(row % 2 == 0) {
					if(row - 1 >= 0) {
						//console.info(row + '，' + col + ' 的右上是：' + (row - 1) + '，' + (col));
						//return map[row - 1][col];
						return new Array(row - 1, col);
					}
				} else {
					if(row - 1 >= 0 && col + 1 < this.cols) {
						//console.info(row + '，' + col + ' 的右上是：' + (row - 1) + '，' + (col + 1));
						//return map[row - 1][col + 1];
						return new Array(row - 1, col + 1);
					}
				}
				return null;
			}

			getRight(row, col) {
				if(col + 1 < this.cols) {
					//console.info(row + '，' + col + ' 的右边是：' + (row) + '，' + (col + 1));
					//return map[row][col + 1];
					return new Array(row, col + 1);
				}
				return null;
			}

			getBottomRight(row, col) {
				if(row % 2 == 0) {
					if(row + 1 < this.rows) {
						//console.info(row + '，' + col + ' 的右下是：' + (row + 1) + '，' + (col));
						//return map[row + 1][col];
						return new Array(row + 1, col);
					}
				} else {
					if(row + 1 < this.rows && col + 1 < this.cols) {
						//console.info(row + '，' + col + ' 的右下是：' + (row + 1) + '，' + (col + 1));
						//return map[row + 1][col + 1];
						return new Array(row + 1, col + 1);
					}
				}
				return null;
			}

			getBottomLeft(row, col) {
				if(row % 2 == 0) {
					if(row + 1 < this.rows && col - 1 >= 0) {
						//console.info(row + '，' + col + ' 的左下是：' + (row + 1) + '，' + (col - 1));
						//return map[row + 1][col - 1];
						return new Array(row + 1, col - 1);
					}
				} else {
					if(row + 1 < this.rows) {
						//console.info(row + '，' + col + ' 的左下是：' + (row + 1) + '，' + (col));
						//return map[row + 1][col];
						return new Array(row + 1, col);
					}
				}
				return null;
			}

			getNeighbors(row, col) {
				let tmp = [];
				tmp.push(this.getLeft(row, col));
				tmp.push(this.getTopLeft(row, col));
				tmp.push(this.getTopRight(row, col));
				tmp.push(this.getRight(row, col));
				tmp.push(this.getBottomRight(row, col));
				tmp.push(this.getBottomLeft(row, col));
				return tmp;
			}

			getNeighborsType(row, col) {
				let tmp = new Array(6);
				let node0 = this.getLeft(row, col);
				let node1 = this.getTopLeft(row, col);
				let node2 = this.getTopRight(row, col);
				let node3 = this.getRight(row, col);
				let node4 = this.getBottomRight(row, col);
				let node5 = this.getBottomLeft(row, col);
				
				tmp[0] = node0 == null ? -1 : this.map[node0[0]][node0[1]];
				tmp[1] = node1 == null ? -1 : this.map[node1[0]][node1[1]];
				tmp[2] = node2 == null ? -1 : this.map[node2[0]][node2[1]];
				tmp[3] = node3 == null ? -1 : this.map[node3[0]][node3[1]];
				tmp[4] = node4 == null ? -1 : this.map[node4[0]][node4[1]];
				tmp[5] = node5 == null ? -1 : this.map[node5[0]][node5[1]];
				
				return tmp;
			}
		}

		document.addEventListener('DOMContentLoaded', function() {
			//debugger;
			const gameBoard = new GameBoard();
			
			const board = document.getElementById('container');
			for (let i = 0; i < gameBoard.rows; i++) {
				let lineDiv = document.createElement('div');
				lineDiv.className = 'line';
				for (let j = 0; j < gameBoard.cols; j++) {
					let itemDiv = document.createElement('div');
					itemDiv.className = 'item';
					itemDiv.dataset.row = i;
					itemDiv.dataset.col = j;
					if(gameBoard.map[i][j] == 1) {
						img = document.createElement('img');
						img.src = 'cat.png';
						img.alt = 'A cute cat';
						itemDiv.appendChild(img);
					} else {
						itemDiv.style.backgroundColor = gameBoard.getBackgroundColor(i, j);
					}
					lineDiv.appendChild(itemDiv);
				}
				lineDiv.addEventListener('click', function(event) {
					if (gameBoard.moveLock == 1) return;
					if(gameBoard.currentRow == 0 || gameBoard.currentCol == 0 || gameBoard.currentRow + 1 == gameBoard.rows || gameBoard.currentCol + 1 ==gameBoard.cols) {
						alert('你输了!');
						return;
					}

					let target = event.target;
					if (target.matches('.item')) {
						let row = target.dataset.row;
						let col = target.dataset.col;
						if (gameBoard.map[row][col] == 0) {
							gameBoard.moveLock = 1;
							gameBoard.updateCell(row, col);
							gameBoard.calCost();
							let rt = gameBoard.calPath(gameBoard.currentRow, gameBoard.currentCol);
							setTimeout(() => {
								if (rt < 0) {
									alert('你赢了!');
									return;
								}
								gameBoard.moveLock = 0;
							}, 500);

							//gameBoard.calPathAsync(gameBoard.currentRow, gameBoard.currentCol).then((result) => {
							//	if (result < 0) {
							//		alert('你赢了!');
							//		return;
							//	}
							//});
						}
					}
				});
				board.appendChild(lineDiv);
			}
		});
    </script>
</body>
</html>